﻿using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace GameLibrary.AI
{
    /// <summary>
    /// Find new opponent
    /// Method: Graph search.
    /// 
    /// problem: each player have a ratio of (opponents' total production)/ player's total income
    ///         opponent's production = opponent's income - opponent's opponents' total production.
    ///         Which lead to a graph with circle.
    ///         
    /// Solve:  use breadth first search change the graph into a tree
    ///         then recursively substract each node's income by its leaf's income
    ///         
    /// recult: Approximate of the remaining productive of opponent.
    ///         that is how many productive power the opponent can use to fight player.
    /// </summary>
    [Serializable]
    public class GetNewDiplomaticRelationship
    {
        private uint PlayerID;
        private Dictionary<uint,float> Incomes;
        private float IncomeRatio;
        Dictionary<uint,Dictionary<uint,DiplomaticRelationshipType>> Relations;

        public GetNewDiplomaticRelationship(
                        uint playerID, // player's id
            Dictionary<uint,float> incomes, // other player's income known by the player above
            float incomeRatio, // how many income can be used for war
            Dictionary<uint,Dictionary<uint,DiplomaticRelationshipType>> relations
            )
        {
            this.PlayerID = playerID;
            this.Incomes = incomes;
            this.IncomeRatio = incomeRatio;
            this.Relations = relations;
        }

        /// <summary>
        /// Return 0 if warspend/income ratio already over limit,
        /// else return player with minimal influence on ratio.
        /// </summary>
        /// <returns></returns>
        public uint GetResult()       
        {
            if (this.Incomes.Count == 0)
                return 0;
            float totalSpend = (from pr in this.Incomes
                                where this.Relations[this.PlayerID][pr.Key] == DiplomaticRelationshipType.War
                                select pr.Value).Sum();

            float ratio = totalSpend / this.Incomes[this.PlayerID];
            if (ratio >= this.IncomeRatio)
                return 0;

            Dictionary<uint, float> idIncomeMap = new Dictionary<uint, float>();
            foreach (var id in from i in this.Relations[this.PlayerID].Keys
                               where this.Relations[this.PlayerID][i]
                                        == DiplomaticRelationshipType.Peace
                               select i
                                   )
            {
                var tree = this.GetTree(id);
                float remaining = this.GetAvaliableIncome(id, tree);
                idIncomeMap.Add(id, remaining);
            }
            var pair = idIncomeMap.Min();
            
            return pair.Key;
        }

        private float GetAvaliableIncome(uint id, AdjancencyList<uint, uint> tree)
        {
            var opponets = tree.Values(id);
            if (opponets.Count() > 0)
            {
                float total = 0;
                foreach (var player in tree.Values(id))
                {
                    total -= GetAvaliableIncome(player, tree);
                }
                return total;
            }
            else
                return this.Incomes[id];
        }

         /// <summary>
         /// use BFS find all 
         /// </summary>
         /// <param name="id"></param>
         /// <returns></returns>   
        private AdjancencyList<uint, uint> GetTree(uint id)
        {
            HashSet<uint> list = new HashSet<uint>(this.Relations[id].Keys);
            AdjancencyList<uint, uint> tree = new AdjancencyList<uint, uint>();
            HashSet<uint> visited = new HashSet<uint>();
            Queue<uint> queue = new Queue<uint>();
            queue.Enqueue(list.First()); 
            while (queue.Count > 0)
            {
                id = queue.Dequeue();
                tree.AddKey(id);
                visited.Add(id);
                foreach (uint key in from i in this.Relations[id].Keys
                                     where list.Contains(i) == true // know by this player , should not count not known party, because I think it is not natural to count something you don't know
                                     && visited.Contains(i) == false // not visited , should not count an income twice
                                     && this.Relations[id][i] == DiplomaticRelationshipType.War // id have war with i 
                                     select i)
                {
                    queue.Enqueue(key);
                    tree.AddValue(id, key);
                    tree.AddKey(key);
                }
            }
            return tree;
        }
    }
}
